package com.lzp.leetcode.stackandqueue;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 有效的括号
 *
 * @author lzp
 * @date 2020/5/31
 */
public class LC20_IsValid {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                char top = stack.pop();
                if (top == '(' && c != ')') {
                    return false;
                }
                if (top == '{' && c != '}') {
                    return false;
                }
                if (top == '[' && c != ']') {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    /**
     * 比较整洁的写法
     * o(n) / o(n)
     *
     * @param s
     * @return
     */
    public boolean isValid2(String s) {
        Stack<Character> stack = new Stack<>();
        Map<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put(']', '[');
        map.put('}', '{');
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsValue(c)) {
                // 左括号
                stack.push(c);
            } else if (stack.isEmpty() || !map.get(c).equals(stack.pop())) {
                // 如果右括号，如果栈空，或者对应左括号与栈顶不一致，返回false
                return false;
            }
        }
        return stack.isEmpty();
    }
}
